package org.example;

import java.util.Stack;
public class PrefixGenerator {
    private Lexer lexer;
    private String currentToken;
    public PrefixGenerator(String expression) {
        // 分解表达式为单独的符号（包括数字、运算符、括号）
        StringBuilder reversedExpression = new StringBuilder();
        StringBuilder currentNumber = new StringBuilder();
        // 反向扫描表达式
        for (int i = expression.length() - 1; i >= 0; i--) {
            char ch = expression.charAt(i);

            // 如果是数字或小数点，加入当前数字
            if (Character.isDigit(ch) || ch == '.') {
                currentNumber.append(ch);
            } else {
                // 遇到操作符或括号时
                if (currentNumber.length() > 0) {
                    // 如果当前数字存在，将其添加到反转表达式中
                    reversedExpression.append(currentNumber.reverse());
                    currentNumber.setLength(0); // 清空当前数字
                }
                // 添加操作符或括号
                reversedExpression.append(ch);
            }
        }
        // 如果有剩余的数字，添加到表达式中
        if (currentNumber.length() > 0) {
            reversedExpression.append(currentNumber.reverse());
        }
        // 使用反转后的表达式初始化 Lexer
        this.lexer = new Lexer(reversedExpression.toString());
        this.currentToken = lexer.nextToken();  // 初始化当前 token
    }

    public String generatePrefix() throws Exception {
        Stack<String> operators = new Stack<>();
        Stack<String> result = new Stack<>();

        while (currentToken != null) {
            // 如果是数字，直接推入结果栈
            if (isNumber(currentToken)) {
                result.push(currentToken);
                currentToken = lexer.nextToken();
            }
            // 右括号，推入运算符栈
            else if (currentToken.equals(")")) {
                operators.push(currentToken);
                currentToken = lexer.nextToken();
            }
            // 左括号，弹出运算符栈中的元素直到遇到右括号
            else if (currentToken.equals("(")) {
                while (!operators.isEmpty() && !operators.peek().equals(")")) {
                    result.push(operators.pop());
                }
                if (!operators.isEmpty() && operators.peek().equals(")")) {
                    operators.pop(); // 弹出右括号
                } else {
                    throw new Exception("不匹配的括号");
                }
                currentToken = lexer.nextToken();
            }
            // 操作符，处理优先级
            else if (isOperator(currentToken)) {
                while (!operators.isEmpty() && hasPrecedence(operators.peek(), currentToken)) {
                    result.push(operators.pop());
                }
                operators.push(currentToken);
                currentToken = lexer.nextToken();
            } else {
                throw new RuntimeException("Unexpected token: " + currentToken);
            }
        }

        // 弹出剩余的运算符
        while (!operators.isEmpty()) {
            result.push(operators.pop());
        }

        // 结果栈中存储的是反转后的前缀表达式
        StringBuilder prefixExpr = new StringBuilder();
        while (!result.isEmpty()) {
            prefixExpr.append(result.pop()).append(" ");
        }

        return prefixExpr.toString().trim();
    }

    private boolean isNumber(String token) {
        try {
            Double.parseDouble(token);
            return true;
        } catch (NumberFormatException e) {
            return false;
        }
    }

    private boolean isOperator(String token) {
        return "+-*/^".contains(token);
    }

    private boolean hasPrecedence(String op1, String op2) {
        if (op2.equals("(") || op2.equals(")")) {
            return false;
        }
        if (op1.equals("^") && !op2.equals("^")) {
            return true;
        }
        if ((op1.equals("*") || op1.equals("/")) && (op2.equals("+") || op2.equals("-"))) {
            return true;
        }
        return false;
    }
}
